CF321E Ciel and Gondolas

各位大佬都用的 $wqs$ 二分，蒟蒻介绍一种简单方法。

$dp$ 式很好列:

$dp[i][j]=min( dp[i-1][k-1] + calc( k , j ) )$

$calc(k,j)$表示将 $k$ 到 $j$ 的贞鱼在同一车的怨气值 ， 决策具有单调性。

不如将当前的决策点区间记为 $ [optl,optr] $ , 处理 $dp$ 的区间为 $ [L,R] $

我们可以暴力计算 $dp[s][mid]$ 的值 $(mid=\frac{L+R}{2})$ ， 并记录当前的决策点$opt$。

然后我们可以递归计算 $dp[s][l...(mid-1)]$ 与 $dp[s][(mid+1)...r]$

因为决策具有单调性 ， 所以计算 $dp[s][l...(mid-1)]$时只需用$[optl,opt]$ , 计算 $dp[s][(mid+1)...r]$时只需用$[opt,optr]$。

这种方法仅适用于有决策单调性的题，时间复杂度为$\Theta(k*n*\log n)$

#include <cstdio>
#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f

void Read( int &x ) {
	x = 0; int f = 1;
	char s = getchar( );
	for( ; s < '0' || s > '9' ; s = getchar( ) ) f = s == '-' ? -f : f;
	for( ; s >= '0' && s <= '9' ; s = getchar( ) ) x = x * 10 + s - '0';
	x *= f;
}
void Write( int x ) {
	if( x < 0 )
		putchar('-') , x = -x;
	if( x >= 10 ) Write( x / 10 );
	putchar( x % 10 + '0' );
}

const int MAXK = 800 , MAXN = 4000;
int n , k , x , sum[ MAXN + 5 ][ MAXN + 5 ];
int dp[ MAXK + 5 ][ MAXN + 5 ];

int Calc( int u , int v ) {
	return sum[ v ][ v ] - sum[ v ][ u - 1 ] - sum[ u - 1 ][ v ] + sum[ u - 1 ][ u - 1 ];
}
void dfs( int s , int L , int R , int optl , int optr ) {
	if( L > R ) return;
	
	int Mid = ( L + R ) / 2 , opt;
	dp[ s ][ Mid ] = INF;
	for( int i = optl ; i <= min( optr , Mid ) ; i ++ ) {
		if( dp[ s ][ Mid ] > dp[ s - 1 ][ i - 1 ] + Calc( i , Mid ) ) {
			dp[ s ][ Mid ] = dp[ s - 1 ][ i - 1 ] + Calc( i , Mid );
			opt = i;
		}
	}
	dfs( s , L , Mid - 1 , optl , opt );
	dfs( s , Mid + 1 , R , opt , optr );
}

int main( ) {
	Read( n ) , Read( k );
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= n ; j ++ )
			Read( x ) , sum[ i ][ j ] = sum[ i - 1 ][ j ] + sum[ i ][ j - 1 ] - sum[ i - 1 ][ j - 1 ] + x;
	for( int i = 1 ; i <= n ; i ++ )
		dp[ 0 ][ i ] = INF;
	for( int i = 1 ; i <= k ; i ++ )
		dfs( i , 1 , n , 1 , n );
	Write( dp[ k ][ n ] / 2 );
	return 0;
}